/*
靓仔阿旭肝了三个小时写出来的力扣，搜索旋转数组！

 */
import java.util.Arrays;

public class Best
{
    public int search(int[] nums, int target)
    {
        int len = nums.length;
        if(len == 1) {  return nums[0]==target ? 0:-1;}
//            if(nums[0] == target)
//                {
//                    return 0;
//                }
//                else
//                {
//                    return -1;
//                }
//            } 关于数组长度为1时候，数组唯一的元素是否是目标值可以简化成上述一句话！
//        if(len==2)
//        {
//            if(nums[0]==target) return 0;
//            else if(nums[1]==target) return 1;
//            else return -1;
//        }//当二分法考虑到拆分后的两个小数组是否长度为1和2时，就不用针对数组长为2时进行特判！
//        //上面几行话也可以注释掉！
            if(nums[0] < nums[len-1])//如果旋转回原状态
             {//正常二分查找，在头尾之外
                if(nums[0] > target || nums[len-1] <target) {return -1;}
                //目标值在大小范围内，直接二分
                return ef(nums, 0, len,target );
            }
            //上述特判都完成后，去找他的区间点啦~~
            int l =0;
            int r =len-1;
            while(l <= r)
            {
                int mid = l+((r-l)>>1);
                //mid落在区间点的左边
                if(nums[mid]>nums[len-1]){l=mid+1;}
                //mid落在区间点的右边
                else { r=mid-1; }
            }
            //退出条件是，右边为l，左边为r，左大右小
            // 这时候你找的的r就是第一个数组的最后一位，身后既是万丈深渊！
        //这时候又找到了区间点，再拿目标值和最大最小值范围进行一次比较！
        //比最大值还大，比最小值还小，别找了，洗洗睡吧
        if(target>nums[r] || target<nums[l]) {  return -1;   }
        int a = ef(nums,0,l-1,target);
        int b = ef(nums,l,len-1,target);

        return a>b?a:b;
        }
        public int ef(int[] nums,int left,int right,int target)
        {
            int l = left;
            int r = right;
            //对截出来的两个数组进行比较~~防止截出来的两个数组长为1或者长为2的
            if(r==l)    { return (nums[r]==target) ? r : -1;}
//                if(nums[r]==target)
//                {
//                    return r;
//                }
//                else
//                {
//                    return -1;
//                }

            if(r-l==1)
            {
                if(nums[l]==target) return l;
                if(nums[r]==target) return r;
                else return -1;
            }//二分查找，尼玛特事特办，一个数组就两个，比较不好反手给你right=mid-1==-1给你来个越界！

            while(l<=r)
            {
                int mid = l+((r-l)>>1);
                if(nums[mid]<target)    l = mid+1;
                else if(nums[mid]>target)   r=mid-1;
                else return mid;
            }
            return -1;

        }
    }



